#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N       4
#define M       3
#define MAX     100
#define MIN     -1

void adjust(int *loser_tree, int *node, int n)
{
    int parent = (n+N)/2, t;

    while (parent > 0) {
        if (node[loser_tree[parent]] < node[n]) {
            t = loser_tree[parent];
            loser_tree[parent] = n;
            n = t;
        }
        parent = parent/2;
    }
    loser_tree[0] = n;
}

int quickpass(int *a, int i, int j)
{
    int x = a[i];

    while (i < j) {
        while (i < j && a[j] >= x)
            j--;
        a[i] = a[j];

        while (i < j && a[i] <= x)
            i++;
        a[j] = a[i];
    }
    a[i] = x;

    return i;
}

int quicksort(int *a, int i, int j)
{
    int k;

    if (i < j) {
        k = quickpass(a, i, j);
        quicksort(a, k+1, j);
        quicksort(a, i, k-1);
    }
}

int main(int argc, char *argv[])
{
    int loser_tree[N];
    int node[N+1];
    int data[N][M+1]; 
    int index[N];
    int i, j;

    srandom(time(NULL));
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            data[i][j] = random()%MAX;
        }
        data[i][j] = MAX;
    }

    for (i = 0; i < N; i++) {
        quicksort(data[i], 0, M-1);
        for (j = 0; j < M; j++) {
            printf("%d ", data[i][j]);
        }
        printf("\n");
    }

    for (i = 0; i < N; i++) {
        index[i] = 0;
        node[i] = data[i][index[i]];
    }
    node[N] = MIN;

    for (i = 0; i < N; i++) {
        loser_tree[i] = N;
    }

    for (i = N-1; i >= 0; i--) {
        adjust(loser_tree, node, i);
    }

    while (node[(i = loser_tree[0])] != MAX) {
        printf("%d ", node[i]);
        index[i] = index[i] + 1;
        node[i] = data[i][index[i]]; 
        adjust(loser_tree, node, loser_tree[0]);
    }
    printf("\n");
    
    return 0;
}
